Data sorting is important and often used in data processing systems as well as in consumer electronics products such as personal computers, facsimile, vehicle navigation systems and the like. In a navigation system, for example, a map data storage such as a DVD (digital versatile disc) stores map data including point of interest (POI) data showing a large number of places categorized by predetermined groups. Examples of category of POIs include ATM, bank, restaurant, gas station, supermarket, and the like.
When a user requested to see a specific type of POIs such as restaurant, a navigation system displays a list of restaurants sorted by distance from a particular position, typically, a current user (vehicle) position. Since a large number of POIs, for example as many as 1,000 POIs, have to be sorted at the same time, the navigation system takes a relatively long time, such as from several to ten seconds or more before displaying the results.
Data sorting is conducted by a computer system such as shown in FIG. 1. In this example, the computer system is comprised of a bus 11 for transfer of data and address, a main memory 12 for storing programs, a processor 13 for executing a program, an input device such as a keyboard 15, a buffer memory 17 for temporary storing data, and a display 18. The sorting method of the present invention is implemented by such a computer system.
There are a large number of known sorting procedures. Generally, when sorting an array of data having a large number of entries, a buffer memory of a large capacity corresponding to such a large number of entries is required for the sorting procedure. Further, to complete the data sorting within a short time, a processor must be capable of high speed operation.
FIGS. 2A-2C are schematic diagrams respectively showing an example of prior art technology which includes an array of input data, a buffer memory used for the sorting procedure, and an array of sorted data. This example shows a case where input data with a large number of entries has to be sorted at the same time, i.e., an overall sorted result has to be produced at the same time. The array of input data in FIG. 2A has ten entries each being provided with a number.
In the case where such entries are POIs (point of interest) data used for a navigation system, the number of each entry represents, for example, a distance of each POI from a particular position, such as a current vehicle position. The data array of FIG. 2C is the result of sorting process where the elements in the data array of FIG. 2A are sorted from the smallest number (ex. shortest distance) to the largest number (ex. longest distance).
To sort the input data of FIG. 2A, the input data has to be stored in the buffer memory of FIG. 2B and data comparison of a large number of times has to be repeated during the sorting procedure. The buffer memory must have sufficient capacity to store the array of input data as a whole. For example, in the case of sorting the POIs information involved in the navigation system, where the number of POIs is as large as 1,000, the buffer memory having a memory capacity of at least 1,000 storage locations must be used. Further, to process such a large size of data by performing a large number of comparison, the sorting procedure takes a long time.
When a number of entries in the input data is N, and if the input data is sorted by a Quick Sort, one of the most commonly used sorting methods, it is proven that it requires the following number of data comparison:Comparison (average)=Nln(N)Comparison (worst case)=N(N−1)/2where ln is the natural logarithm.
Thus, when N is 1,000, the number of comparison is about 6,900 in the average case. In the worst case (input list is in the reverse order of the final result of sorting), the number of comparison is about 500,000. Accordingly, the conventional sorting method requires a long processing time as well as a buffer memory of large memory capacity. Therefore, there is a need for a new data sorting method which can sort the data quickly without requiring a large size buffer memory and/or a high speed processor.